#include <string.h>

#include <iostream>
using std::cout;
using std::endl;

// 数组实现栈（顺序栈）
template <typename T>
class ArrayStack {
 public:
  ArrayStack(int init_size) {
    if (init_size <= 0) init_size = 2;
    arr_ = new T[init_size];
    size_ = init_size;
    top_ = 0;  // top位于最后一个元素的后一个位置
  }
  ~ArrayStack() { delete[] arr_; }

  void Push(const T& data) {
    if (top_ >= size_) {
      int newsize = size_ * 2;
      T* newarr = new T[newsize];
      memcpy(&newarr[0], &arr_[0], size_ * sizeof(T));
      delete[] arr_;
      arr_ = newarr;
      size_ = newsize;
    }
    arr_[top_++] = data;
  }

  bool Pop(T& data) {
    if (top_ == 0) return false;
    data = arr_[--top_];
    return true;
  }

  bool Peek(T& data) {
    if (top_ == 0) return false;
    data = arr_[top_ - 1];
    return true;
  }

  int size() const { return size_; }

  void Print() {
    cout << "size:" << size_ << "----";
    for (int i = 0; i < top_; ++i) {
      cout << arr_[i] << ' ';
    }
    cout << endl;
  }

 private:
  int size_;
  T* arr_;
  int top_;
};

void TestArrayStack() {
  ArrayStack<int> stack(2);
  stack.Push(1);
  stack.Push(2);
  stack.Push(3);
  stack.Push(4);
  stack.Push(5);
  stack.Print();
  for (int i = 0; i < 2; ++i) {
    int out;
    if (stack.Pop(out)) cout << out << ',';
  }
  cout << endl;
  stack.Print();
}

// 链表节点
typedef int DataType;
struct Node {
  DataType data;
  Node* next;
  Node(const DataType& d) {
    data = d;
    next = nullptr;
  }
};

// 链表实现栈（链式栈）
class ListStack {
 public:
  ListStack() : head_(nullptr) {}
  ~ListStack() {
    Node* p = head_;
    while (p && p->next) {
      Node* todel = p;
      p = p->next;
      delete todel;
    }
    if (p) delete p;
  }

  void Push(const DataType& data) {
    Node* node = new Node(data);
    node->next = head_;
    head_ = node;
  }

  Node* Pop() {
    if (head_ == nullptr) return nullptr;
    Node* ret = head_;
    head_ = head_->next;
    return ret;
  }

  void Print() {
    Node* p = head_;
    while (p) {
      cout << p->data << ' ';
      p = p->next;
    }
    cout << endl;
  }

 private:
  Node* head_;
};

void TestListStack() {
  ListStack stack;
  stack.Push(1);
  stack.Push(2);
  stack.Push(3);
  stack.Push(4);
  stack.Print();
  for (int i = 0; i < 2; ++i) {
    Node* node = stack.Pop();
    if (node) {
      cout << node->data << ',';
      delete node;
    }
  }
  cout << endl;
  stack.Print();
}

int main() {
  TestArrayStack();
  TestListStack();
}